GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Bullyalgorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Bullyalgorithmus</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Der <b>Bullyalgorithmus</b> ist ein <a href="Rekursion" title="Rekursion">rekursiver</a>, verteilter <a href="Algorithmus" title="Algorithmus">Algorithmus</a> der in einem <a href="Verteiltes_System" title="Verteiltes System">verteilten System</a> verwendet wird, wenn ein neuer Koordinatorprozess ermittelt werden muss, weil der ursprüngliche abgestürzt ist. Letzteres kann beispielsweise durch einen Timeout festgestellt werden.

</p>

<div class="mw-heading mw-heading2"><h2 id="Ablauf">Ablauf</h2></div>

<p>Ein <a href="Prozess_(Informatik)" title="Prozess (Informatik)">Prozess</a> p, welcher den Ausfall des Koordinators bemerkt hat, sendet Anfragen an alle Prozesse, die eine höhere ID haben als er selbst. Diese Prozesse schicken eine Bestätigung zurück, wenn sie nicht selbst abgestürzt sind. Falls der Prozess p von Prozessen mit höherer ID Antworten bekommt, sendet er keine weiteren Nachrichten mehr. Falls Prozess p keine Antwort bekommt wird er selbst zum Koordinator.

</p><p>Jeder Prozess (mit höherer ID), der p geantwortet hat, verschickt seinerseits wiederum Anfragen an alle Prozesse, die eine höhere ID haben als er, um herauszufinden ob diese noch existieren, was diese dann ebenso wiederholen (Rekursion). Der letzte Prozess hat keinen Prozess mehr, den er fragen kann, da er selbst die höchste ID hat, denn der Koordinatorprozess mit der höchsten ID ist ja ausgefallen und kann nicht mehr antworten. Er tritt selbst an die Stelle des neuen Koordinators und sendet per Broadcast die Nachricht, dass er der neue Koordinator sei.

</p>

<div class="mw-heading mw-heading3"><h3 id="Annahmen">Annahmen</h3></div>

<p>Damit der Bullyalgorithmus beweisbar funktioniert, müssen in dem verteilten System folgende Annahmen gelten:

</p>

<ul><li>Alle Prozesse kooperieren und verwenden exakt denselben Wahlalgorithmus.</li>

<li>Es gibt keine Fehler in der Implementierung und alle Prozesse bieten auch ständig die Möglichkeit an, empfangene Nachrichten abzuarbeiten.</li>

<li>Wenn ein Prozess P1 die Nachricht M von Prozess P2 erhält, dann ist sichergestellt, dass die Nachricht zu einem früheren Zeitpunkt gesendet worden ist. Es gibt also keine spontan generierten Nachrichten im System.</li>

<li>Alle Prozesse besitzen so genannte "Storage Cells", in denen die Daten gespeichert werden, an denen sie arbeiten. Das bedeutet, dass selbst bei einem Fehler oder Ausfall des Prozesses die Daten gespeichert bleiben. Datenzugriff in "Storage Cells" sollte auf <a href="Transaktion_(Informatik)" title="Transaktion (Informatik)">Transaktionen</a> basieren – entweder die neuen Daten werden in die Storage Cell geschrieben oder sie werden verworfen, die alten bleiben aber erhalten und weiterhin konsistent.</li>

<li>Wenn ein Prozess ausfällt, hört er sofort mit der Bearbeitung seiner Daten auf. Wird er wieder aktiviert, fängt er mit der Bearbeitung wieder an (dort, wo er aufgehört hat).</li>

<li>Es gibt keine Übertragungsfehler im System. Das bedeutet, dass alle Nachrichten korrekt übertragen werden.</li>

<li>Alle Nachrichten werden in der Reihenfolge ihrer Ankunft abgearbeitet. Sendet Prozess 1 also die Nachrichten M1 und M2 in dieser Reihenfolge, so wird ein zweiter Prozess diese Nachrichten auch in der Reihenfolge M1, M2 abarbeiten.</li>

<li>Es gibt keine Ausfälle in der Kommunikation und das System bietet eine zeitliche Obergrenze T an, zu der die Nachricht auf jeden Fall abgearbeitet werden sollte. Wenn ein Prozess also nach T Zeiteinheiten noch immer keine Antwort von einem anderen erhalten hat, so kann er davon ausgehen, dass der Empfängerprozess abgestürzt ist.</li>

<li>Ein Prozess hört niemals auf, auf Nachrichten zu antworten und tut dies auch ohne Verzögerung.</li>

<li>Das Netzwerk des Systems arbeitet synchron.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<p>P bemerkt, dass der Koordinator nicht mehr antwortet<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>:

</p>

<pre>function hold_election()

for each (Process Q) {

if (Id(Q) > Id(P))

send(Q, ELECTION);

end if

}

</pre>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \exists }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/77ed842b6b90b2fdd825320cf8e5265fa937b583.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.293ex; height:2.176ex;" alt="{\displaystyle \exists }" loading="lazy"></span> Q: (receive(Q, ANSWER)) //timeout T for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \exists }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \exists }</annotation>

</semantics>

then

do_something_else();

else

for each (Process Q) {

if (Id(Q) < Id(P))

send(Q, COORDINATOR);

endif

}

endif

</pre>

<p>P empfängt <i>ELECTION</i>, gesendet von Prozess <i>pred</i>:

</p>

<pre>function continue_election()

send(pred, ANSWER);

hold_election();

</pre>

<div class="mw-heading mw-heading3"><h3 id="Vorteile">Vorteile</h3></div>

<ul><li>Es ist problemlos möglich einen ausfallenden Koordinator zu ersetzen, da jeder Prozess die Ermittlung eines neuen Koordinatorprozesses anstoßen kann.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Nachteile">Nachteile</h3></div>

<ul><li>Alle Prozesse müssen jedem Prozess bekannt sein und es muss eine absolute Ordnung auf den Prozessen bestehen. Ansonsten kann kein Prozess ermitteln, welche Nachrichten er verschicken muss.</li>

<li>Reagiert ein Prozess sehr langsam, entsteht hierdurch eine Verzögerung, die den gesamten Ablauf verlangsamt.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Emmett Witchel: <a rel="nofollow" class="external text" href="https://www.cs.utexas.edu/users/witchel/372/lectures/25.DistributedCoordination.ppt"><i>Distributed Coordination.</i></a> 2005, PPT-Datei, abgerufen am 3. August 2013.</li>

<li>Hector Garcia-Molina: <i>Elections in a Distributed Computing System.</i> In: <i><a href="IEEE" class="mw-redirect" title="IEEE">IEEE</a>. Transactions on Computers.</i> Bd. C-31, No. 1, Januar 1982, <span class="-print"><a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220018-9340%22&key=cql">0018-9340</a></span></span>, S. 48–59, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1109/TC.1982.1675885">10.1109/TC.1982.1675885</a></span>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://inet.haw-hamburg.de/teaching/ws-2012-13/verteilte-systeme/verteilte-systeme">Vorlesung „Verteilte Systeme“</a> an der <a href="Hochschule_f%C3%BCr_Angewandte_Wissenschaften_Hamburg" title="Hochschule für Angewandte Wissenschaften Hamburg">Hochschule für Angewandte Wissenschaften Hamburg</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://inet.haw-hamburg.de/teaching/ws-2012-13/verteilte-systeme/06_WahlenWA.pdf">Folie 5, Vorlesung "Verteilte Systeme" Wintersemester 2013/13</a> (PDF; 1,6 MB) - Dept. Informatik, <a href="HAW_Hamburg" class="mw-redirect" title="HAW Hamburg">HAW Hamburg</a>, abgerufen am 8. Juli 2013</span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-07-01" href="https://de.wikipedia.org/wiki/?title=Bullyalgorithmus&oldid=257537921">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>